Computer processors contain arithmetic, logic, and control circuitry that interpret and execute instructions from a computer program. Referring to FIG. 1, a typical computer system includes a microprocessor (22) having, among other things, a CPU (24), a memory controller (26), and an on-board cache memory (30). The microprocessor (22) is connected to external cache memory (32) and a main memory (34) that both hold data and program instructions to be executed by the microprocessor (22). Internally, the execution of program instructions is carried out by the CPU (24). Data needed by the CPU (24) to carry out an instruction are fetched by the memory controller (26) and loaded into internal registers (28) of the CPU (24). Upon command from the CPU (24), the memory controller (26) searches for the data first in the fast on-board cache memory (30), then in external cache memory (32), and finally in the slow main memory (34). Finding the data in the cache memory is referred to as a “hit.” Not finding the data in the cache memory is referred to as a “miss.”
The time between when a CPU requests data and when the data is retrieved and available for use by the CPU is termed the “latency” of the system. If requested data is found in cache memory, i.e., a data hit occurs, the requested data can be accessed at the speed of the cache and the latency of the system is reduced. If, on the other hand, the data is not found in cache, i.e., a data miss occurs, and thus the data must be retrieved from main memory for access and the latency of the system is increased.
In the pursuit of improving processor performance, designers have sought two main goals: making operations faster and executing more operations in parallel. Making operations faster can be approached in several ways. For example, transistors can be made to switch faster and thus propagate signals faster by improving semiconductor processes; execution-unit latency can be reduced by increasing the number of transistors in the design; and the levels of logic required by the design to implement a given function can be minimized to increase speed. To execute more operations in parallel, designers mainly rely on one, or a combination of pipelining and superscalar techniques. Pipelined processors overlap instructions in time on common execution resources. Superscalar processors overlap instructions in space on separate resources.
Pipeline stalls are a main performance inhibitor with regard to parallel processing. Stalls arise from data dependencies, changes in program flow, and hardware resource conflicts. At times, pipeline stalls can be avoided by rearranging the order of execution for a set of instructions. Compilers can be used to statically reschedule instructions. However, incomplete knowledge of run-time information reduces the effectiveness of static rescheduling. In-order processors, i.e., processors that issue, execute, complete, and retire instructions in strict program order, have to rely entirely on static rescheduling and thus are prone to pipeline stalls.
As a result, designers use out-of-order processors and seek to implement dynamic instruction rescheduling. The simplest out-of-order processors issue instructions in order but allow them to execute and complete out of order. Even these simple out-of-order processors require complex hardware to reorder results before the corresponding instructions are retired. A strict result order is not required from a data-flow perspective. However, such ordering is necessary to maintain precise exceptions and to recover from mispredicted speculative execution.
A well-known method of reordering is through the use of a reorder buffer, i.e., a buffer that maintains results until written to the register file in program order. Designers also use other types of reordering hardware, such as history buffers and future files. History buffers record source-operand history so the processor can backtrack to a precise architectural state and future files store the current state and the architectural state in separate register files allowing the processor to be restored to a precise check-point state.
Branch prediction and speculative execution are additional techniques used to reduce pipeline stalls. In a pipelined processor, the outcomes of branch instructions are often determined after subsequent instructions have been fetched. Using branch prediction schemes, microprocessors attempt to accurately predict whether a branch is taken or not based on how that branch has behaved previously. The aggregate behavior, or the average behavior over time, of the branch instruction is stored in a Branch Prediction Table (“BPT”). Given a branch instruction's aggregate behavior, the branch predictor, which resides in an instruction fetch unit, predicts the outcome of the branch instruction and then loads instructions thereafter based on that prediction. For example, if the branch predictor predicts that a branch will be taken, then the processor fetches subsequent instructions according to the address to which the instruction branches. When the branch proceeds in the predicted direction, pipeline stalls are completely avoided. On the other hand, if the branch direction is mispredicted, all the instructions after the mispredicted instruction must be removed from the processor.
Modern microprocessors incorporate a variety of branch prediction schemes. These schemes usually fall under one of two broad classifications: static branch prediction and dynamic branch prediction. Static branch prediction occurs when a branch predictor makes predictions that are not based on the run-time behavior of branch instructions. Two such schemes are: “predict not taken” and “predict taken.” In the “predict not taken” scheme, a branch is predicted as not taken, and the processor simply continues as if the branch did not exist. In the “predict taken” scheme, as soon as the branch is decoded and the target address of the next instruction is predicted, it is assumed that the branch is taken and the process continues with the fetching and executing of instructions at the target address.
Dynamic branch prediction, on the other hand, occurs when the processor responds to changes in a branch instruction's behavior while a program is executing. In other words, a dynamic branch prediction scheme provides a mechanism by which a processor can take into account the cumulative behavior of a branch instruction. In cases where there are more than one branch instruction in an instruction bundle, also known as a fetch bundle, some schemes may break the fetch bundle at the points where additional branch instructions reside.
Typically, dynamic branch prediction schemes are extended to predict multiple branches. The increasing number of instructions executed per cycle in high-performance microprocessors calls for the instruction fetch unit to fetch a correspondingly larger number of instructions each cycle. Fetching more instructions per cycle increases the likelihood that more than one branch prediction will need to be made each cycle to determine the next fetch address. Accordingly, a microprocessor handles multiple branch instructions through a multiple branch prediction scheme.
Multiple branch prediction schemes usually depend upon a fetch bundle address (FBA), i.e., the address of the first instruction fetched in a given cycle, to index all prediction structures for the fetched instruction bundle. Each branch to be predicted in the current fetch bundle uses information from the prediction structures indexed by the address of the bundle currently being fetched. In other words, an instruction uses its fetch bundle address to base its index address, which it uses to index a branch prediction structure.
An index based upon the fetch bundle address has typically been used to select several prediction counters from which multiple branch predictions are made dependent upon the location of the branches in the fetch bundle. These counters may be simple two-bit counters with saturation. Typically, the counter is incremented when the branch instruction is taken and it is decremented when the instruction is not taken. For example, the branch instruction could be taken if the counter is in state 2 or 3, and not taken if the counter is in state 0 or 1. The saturation attribute inhibits the counter from recycling. For example, if the counter is in state 3 and a branch instruction is taken, the counter will stay in state 3 and not increment back to state 0. This mechanism attempts to predict branch instructions by gathering and representing the aggregate behavior of previous branch instructions. Improvements made to this mechanism include using branch history so that the processor recognizes repetitive patterns in previous branch instructions to predict later branch instructions.
Typically, branch history mechanisms are separated into two types: global branch history and local branch history. Global branch history pertains to the last g outcomes of executed branch instructions. Local branch history incorporates the last l outcomes of the current branch instruction.
Branch instructions can either be conditional or unconditional. All conditional branch instructions and most unconditional branch instructions can be incorporated into branch history registers. However, some unconditional branch instructions, such as call and return statements, are usually not incorporated into branch history registers. Global branch history prediction schemes have been extended to predict the outcomes of multiple branch instructions. Additionally, in order to predict multiple conditional branch instructions simultaneously, the BPT is typically extended to contain several n-bit counters per entry. Depending on the location of branches in the current fetch bundle, the proper n-bit counters are referenced to make the multiple branch predictions.
FIG. 2 depicts instruction addresses A through A+9, which constitute an exemplary instruction fetch bundle. An instruction address is the location of where an instruction resides in memory. The two exemplary instruction fetch blocks are indexed A (36) and A+5 (40). If the branch instruction resides at A+4 (38), and the branch is predicted taken and mispredicted, the instruction at A+6 (42) uses A+5 (40) as its index address. Alternatively, if a branch instruction is mispredicted, then a subsequent branch instruction depends on a new fetch bundle address to base its index address. Therefore, the prediction information associated with the subsequent branch instruction is different than the prediction information it would have used if it used a prior fetch bundle address. This is due to the fact that the subsequent branch instruction uses prediction information that is based on a newly indexed branch prediction table. One skilled in the art will appreciate that the described method is illustrative of one typical indexing method and, depending on the processor architecture, other methods can be used to index instructions.